package sort;

import java.util.Arrays;
import java.util.Stack;

public class QuickSotrOptimize {
    //快速排序优化：三数取中，该优化主要是针对趋于有序的数组采用快速排序进行的优化，
    //只需要在原本的基础上加上三数取中，也就是将left到right的中间元素与left的元素交换
    public static void main(String[] args) {
        int[] arr = {18,25,2,82,1,38,96,69,15,84,16,35,79,28,39,46,13,79,52,37,19,37,67,49,28,15,19,16,24,35,36,37,38,39};
//        quickSorthreeNum(arr);
        //使用非递归的快速排序
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSorthreeNum(int[] arr){
        quick1(arr,0,arr.length - 1);
    }
    //先进行三数取中,对left,right和mid三个下标对应的中间值的下标进行返回，后续将该下标的值与left下标的值进行交换，以实现对于有序数组就打破有序顺序
    public static int threeNum(int[] arr,int left,int right){
        int mid = (left + right) / 2;
        if (arr[left] < arr[right]){
            if (arr[mid] < arr[left]){
                return left;
            }else if (arr[mid] > arr[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if (arr[mid] <arr[right]){
                return right;
            }else if(arr[mid] > arr[left]){
                return left;
            }else {
                return mid;
            }
        }
    }
    //进行递归
    public static void quick(int[] arr,int left,int right){
        if (right - left <= 0){
            return;
        }
        //三数取中
        int mid = threeNum(arr,left,right);
        swap(arr,left,mid);
        int div = parttion(arr,left,right);
        quick(arr,left,div);
        quick(arr,div + 1,right);
    }
    //求基准：使用hare或者挖坑法,优先使用顺序：挖坑法>hoare>前后指针
    public static int parttion(int[] arr,int left,int right){
        int pivot = arr[left];
        int i = left;
        int j = right;
        while (i < j){
            while (i < j && arr[j] >= pivot){
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }
    public static void swap(int[]arr, int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] =tmp;
    }
    //当数据很多，需要不断进行递归，低递归后面，每次递归的区间就会变得很小，此时小区间也会趋于有序，此时使用直接插入排序会快很多，所以继续优化
    //进行递归
    public static void quick1(int[] arr,int left,int right){
        if (right - left <= 0){
            return;
        }
        if (right - left + 1 <= 20){
            //直接插入排序
            insertSort(arr,left,right);
            return;
        }
        //三数取中
        int mid = threeNum(arr,left,right);
        swap(arr,left,mid);
        int div = parttion(arr,left,right);
        quick1(arr,left,div);
        quick1(arr,div + 1,right);
    }
    //直接插入排序
    public static void insertSort(int[] arr,int left,int right){
        for (int i = left + 1; i <= right; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if (arr[j] > tmp){
                    arr[j + 1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    /**
     * 非递归实现快速排序
     */
    public static void quickSort(int[] arr){
        int left = 0;
        int right = arr.length - 1;

        if (right - left + 1 <= 20){
            //直接插入排序
            insertSort(arr,left,right);
            return;
        }
        //三数取中
        int mid = threeNum(arr,left,right);
        swap(arr,left,mid);

        Stack<Integer> stack = new Stack<>();
        int div = parttion(arr, left, right);
        if(left < div - 1){
            stack.push(left);
            stack.push(div - 1);
        }
        if (right > div + 1){
            stack.push(div + 1);
            stack.push(right);
        }

        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();

            if (right - left + 1 <= 20){
                //直接插入排序
                insertSort(arr,left,right);
//                return;
            }else {
                //三数取中
                mid = threeNum(arr,left,right);
                swap(arr,left,mid);

                div = parttion(arr, left, right);
                if(left < div - 1){
                    stack.push(left);
                    stack.push(div - 1);
                }
                if (right > div + 1){
                    stack.push(div + 1);
                    stack.push(right);
                }
            }
        }

    }
}
